package binary_tree

// 输入某二叉树的前序遍历和中序遍历结果。请重建该二叉树
// 输入的前序遍历，中序遍历的结果中都不包含重复的数字

func Construct(preorder, inorder []int) *TreeNode {
	if len(preorder) == 0 || len(inorder) == 0 {
		return nil
	}
	return constructCore(preorder, inorder)
}

func constructCore(preorder, inorder []int) *TreeNode {
	var rootValue = preorder[0]
	root := &TreeNode{}
	root.val = rootValue
	root.left = nil
	root.right = nil

	inorderRootIndex := -1
	for i := 0; i < len(inorder); i++ {
		if inorder[i] == rootValue {
			inorderRootIndex = i
			break
		}
	}
	if inorderRootIndex == -1 {
		return root
	}
	leftInorderNodes := make([]int, 0)
	if inorderRootIndex >= 1 {
		for i := 0; i < inorderRootIndex; i++ {
			leftInorderNodes = append(leftInorderNodes, inorder[i])
		}
	}

	rightInorderNodes := make([]int, 0)
	if inorderRootIndex < len(inorder)-1 {
		for i := inorderRootIndex + 1; i < len(inorder); i++ {
			rightInorderNodes = append(rightInorderNodes, inorder[i])
		}
	}

	leftPreorderNodes := make([]int, 0)
	if inorderRootIndex >= 1 {
		for i := 1; i < inorderRootIndex+1; i++ {
			leftPreorderNodes = append(leftPreorderNodes, preorder[i])
		}
	}

	rightPreorderNodes := make([]int, 0)
	if inorderRootIndex < len(inorder)-1 {
		for i := inorderRootIndex + 1; i < len(preorder); i++ {
			rightPreorderNodes = append(rightPreorderNodes, preorder[i])
		}
	}

	if len(leftPreorderNodes) > 0 && len(leftInorderNodes) > 0 {
		root.left = constructCore(leftPreorderNodes, leftInorderNodes)
	}
	if len(rightPreorderNodes) > 0 && len(rightInorderNodes) > 0 {
		root.right = constructCore(rightPreorderNodes, rightInorderNodes)
	}

	return root
}
